'''
Created on Jul 6, 2011

@author: vakumar
'''
from com.utils.util import Utils

def Left(i):
    return 2*i + 1

def Right(i):
    return 2*(i + 1)

def Parent(i):
    return (i-1)/2


class heap():
    
    MAX = 'max-heap'
    MIN = 'min-heap'
    
    def __init__(self,arr):
        self.arr = arr
        self.heapsize = len(arr)
        
    def getheap(self, heaptype = MAX):
        return [min_heap(self.arr),
                max_heap(self.arr)][heaptype == heap.MAX] 

    def heapify(self, i):
        pass
    
    def build_heap(self):
        pass    
    
class max_heap(heap):
    def __init__(self, arr):
        heap.__init__(self, arr)
    
    def heapify(self,i):
        self.__max_heapify(i)
        
    def build_heap(self):
        self.__build_max_heap()
    
    def __max_heapify(self, i):
        if i > self.heapsize - 1:
            return
        l = Left(i)
        r = Right(i)
        ### L indicates current index of largest element.
        L = i
        if l < self.heapsize and self.comp(self.arr[L], self.arr[l]):
            L = l
        if r < self.heapsize and self.comp(self.arr[L], self.arr[r]):
            L = r
        if not L == i:
            self.arr[i], self.arr[L] = Utils.swapval(i, L, self.arr)
            self.__max_heapify(L)
    
    def __build_max_heap(self):
        size = len(self.arr)
        i = (size -1)/2
        while i >= 0:
            self.__max_heapify(i)
            i -= 1 

    
class min_heap(heap):
    def __init__(self,arr):
        heap.__init__(self, arr)

    def heapify(self,i):
        self.__min_heapify(i)
        
    def build_heap(self):
        self.__build_min_heap()
    
    def __min_heapify(self, i):
        if i > self.heapsize - 1:
            return
        l = Left(i)
        r = Right(i)
        min = i
        if l < self.heapsize and self.comp(self.arr[l], self.arr[min]):
            min = l
        if r < self.heapsize and self.comp(self.arr[r], self.arr[min]):
            min = r
        if not min == i:
            self.arr[i], self.arr[min] = Utils.swapval(i, min, self.arr)
            self.__min_heapify(min)
    
    def __build_min_heap(self):
        size = len(self.arr)
        i = (size -1)/2
        while i >= 0:
            self.__min_heapify(i)
            i -= 1         
    



    
class HeapSorter(object):
    
    def __init__(self, arr):
        self.arr = arr           
            
    def __heapsort(self):
        self.heap = heap(self.arr).getheap(heap.MAX)
        self.heap.comp = self.comp
        self.heap.build_heap()
        for i in xrange(len(self.arr) -1,0,-1):
            self.arr[0], self.arr[i] =  Utils.swapval(0, i, self.arr)
            self.heap.heapsize -= 1
            self.heap.heapify(0)
            
    def dosort(self):
        print '*'*20
        print 'Heap Sort'
        print '*'*20
        print 'before sort : %s' %str(self.arr)
        self.comp = Utils.comparator() 
        self.__heapsort()
        print 'after sort : %s' %str(self.arr)
        print 'Comparision Performed:: %s' %Utils.count
        self.count = Utils.count 
        
    def getComparisonCount(self):
        return self.count 
        
    def sort(self):
        self.comp = Utils.comparator()
        self.__heapsort()  
        self.count = Utils.count 
        
if __name__ == '__main__':
    arr = [3,4,2,7,1,9,5]
    q = HeapSorter(arr)
    q.dosort()
        